Problem :

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1 :

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2 :

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3 :

Input: temperatures = [30,60,90]
Output: [1,1,0]

核心思維 :

1. 設定n為陣列的大小
2. 若陣列只有一個元素，回傳 { 0 }
3. 使用堆疊儲存索引，把第一天的索引放入堆疊，接著設定回傳的陣列，大小與溫度陣列相同
4. 從第二天開始遍歷溫度陣列

• 若堆疊不為空且當前天的溫度高於堆疊頂部的溫度時，計算堆疊頂部的索引到當前天的距離，接著移出堆疊頂部索引。
• 將當前天的索引放入堆疊並進入下一天

5. 回傳陣列

程式碼 :

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // 設定n為溫度陣列的大小
        const int n = temperatures.size();
        // 若陣列中只有一個元素，則返回 {0}，因為沒有更高的溫度
        if(n == 1){
            return {0};
        }
        // 使用堆疊來儲存索引
        stack<int> s;
        // 將第一天的索引放入堆疊
        s.push(0);
        // 設定回傳的陣列，大小與溫度陣列相同
        vector<int> ans(n);
        // 從第二天開始遍歷溫度陣列
        int i = 1;
        while(!s.empty() && i < n) {
            // 若堆疊不為空且當前天的溫度高於堆疊頂部的溫度時
            while(!s.empty() && i < n && temperatures[i] > temperatures[s.top()]) {
                // 計算堆疊頂部的索引到當前天的距離
                ans[s.top()] = i - s.top();
                // 移出堆疊頂部索引
                s.pop();
            }
            // 將當前天的索引放入堆疊
            s.push(i);
            // 進入下一天
            i++;
        }
        // 回傳陣列
        return ans;
    }
};

結論 :

這題的主要目的是計算每一天距離下一次溫度上升的天數，首先設定陣列大小並檢查陣列中是否只有一個元素，若只有一個元素則返回 { 0 } ，因為無法找到更高的溫度，後面再設定一個與溫度陣列同大小的回傳陣列，並從第二天開始遍歷溫度陣列，之後利用遍歷計算出每一天距離下次溫度上升的天數，最後回傳帶有結果的陣列，這裡活用堆疊操作簡單的特性，利用索引的放入與移出將問題解決。